package com.zhangx.datastructure.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 邻接矩阵P224
 * 数组+矩阵
 * 邻接多重表类似于有向图中的十字链表
 * P240查询
 */
public class MGraph {
    int MAXVEX = 5;
    int INFINITY = 1000;
//    顶点
    Vertex[] vexs = new Vertex[MAXVEX];
//    邻接矩阵
    int[][] arc = new int[MAXVEX][MAXVEX];

    /**
     * 查询时候看每个定点是否有访问过
     */
    boolean[] visited = new boolean[MAXVEX];

    int numVertexes;//顶点数
    int nunEdges;//边数

    public MGraph(){
//        初始化数据 用P239 7-5-2的图
        MAXVEX = 9;
        numVertexes = MAXVEX;
        vexs = new Vertex[MAXVEX];
        visited = new boolean[MAXVEX];
//        大写A
        short start = 65;
        for (int i = 0; i < vexs.length; i++) {
            Vertex vertex = new Vertex(Character.toString((char)start));
            start++;
            vexs[i] = vertex;
        }

//        构建邻接矩阵
        arc = new int[MAXVEX][MAXVEX];
        for (int i = 0; i < arc.length; i++) {
            for (int j = 0; j < arc[0].length; j++) {
                arc[i][j] = 0;
            }
        }
//          A B C D E F G H I
//        A 0 1 0 0 0 1 0 0 0
//        B 1 0 1 0 0 0 1 0 1
//        C 0 1 0 1 0 0 0 0 1
//        D 0 0 1 0 1 0 1 1 1
//        E 0 0 0 1 0 1 0 1 0
//        F 1 0 0 0 1 0 1 0 0
//        G 0 1 0 1 0 1 0 1 0
//        H 0 0 0 1 1 0 1 0 0
//        I 0 1 1 1 0 0 0 0 0
    }
    public void addEdges(String line){
        line = line.toUpperCase();
        char s = line.charAt(0);
        char e = line.charAt(1);
        int i = ((short)s)-65;
        int j = ((short)e)-65;
        arc[i][j] = 1;
        arc[j][i] = 1;
    }

    @Override
    public String toString() {
        System.out.println("  A B C D E F G H I");
        for (int i = 0; i < arc.length; i++) {
            String line = Character.toString((char)((short)(i+65)));
            for (int j = 0; j < arc[i].length; j++) {
                line = line + " " + arc[i][j];
            }
            System.out.println(line);
        }
        System.out.println("vexs=" + Arrays.toString(vexs));
        System.out.println("visited=" + Arrays.toString(visited));
        return "MGraph{" +
                "MAXVEX=" + MAXVEX +
                ", INFINITY=" + INFINITY +
                ", numVertexes=" + numVertexes +
                ", nunEdges=" + nunEdges +
                '}';
    }

    /**
     * 顶点
     */
    class Vertex{

        private String data;

        public Vertex(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "data='" + data + '\'' +
                    '}';
        }
    }


    /**
     * 深度优先查询递归
     * @param i
     */
    void DFS(int i){
        visited[i] = true;//这个顶点被访问过
        System.out.println("当前访问到"+vexs[i]);
        for (int j = 0; j < numVertexes; j++) {
//            如果i j联通且J没被访问过
            if (arc[i][j] == 1 && !visited[j]){
//                查找j的第临近
                DFS(j);
            }
        }
    }

    /**
     * 深度遍历操作
     */
    void DFSTraverse(){
//        全初始化为未访问状态
        for (int i = 0; i < numVertexes; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < numVertexes; i++) {
            if (!visited[i]){
//                实际只会一次，因为递归后就变成访问状态了
                System.out.println("因为"+i+"节点未访问，开始递归");
                DFS(i);
            }
        }

    }

    /**
     * 广度优先
     * 一层一层的查找
     */
    void BFSTarverse(){
        int i = 0,j = 0;
        Queue<Integer> q = new LinkedList<>();
        for (i = 0; i < numVertexes; i++) {
            visited[i] = false;
        }
//        便利每一个定点
        for (i = 0; i < numVertexes; i++) {
            if (!visited[i]){
                visited[i] = true;
                String data = vexs[i].data;
                System.out.println(vexs[i].data);
//                队列，先进先出
                q.offer(i);
                while (!q.isEmpty()){
//                    不断循环队列中的节点，找到他的联通节点
                    i = q.poll();
                    for (j = 0; j < numVertexes; j++) {
//                        找到每个节点的联通节点
//                        如果这个联通节点没被访问过就加入队列
                        if (arc[i][j]==1 && !visited[j]){
                            visited[j] = true;
                            String data2 = vexs[j].data;
                            System.out.println(data2);
                            q.offer(j);
                        }
                    }
                }
            }
        }

    }


    public static void main(String[] args) {
        MGraph mGraph = new MGraph();
        String[] lines = new String[]{"AB","AF","BC","BI","BG","CI","CD","DI","DG","DH","DE","EH","EF","FG","GH"};
        for (String l:lines) {
            mGraph.addEdges(l);
        }
//        System.out.println(mGraph);
//        mGraph.DFSTraverse();
        mGraph.BFSTarverse();

    }
}
